package leetcode.other.greedy;

/**
 * @Description: https://leetcode.cn/problems/candy/
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 *
 * 你需要按照以下要求，给这些孩子分发糖果：
 *
 * 每个孩子至少分配到 1 个糖果。
 * 相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 *
 * @Author Ammar
 * @Create 2023/7/5 14:50
 */
public class _135_分发糖果 {
        public static void main(String[] args) {
            System.out.println(new _135_分发糖果().candy(new int[]{1, 0, 2}));
        }

        public int candy(int[] ratings) {
            int[] candies = new int[ratings.length];
            candies[0] = 1;
            // 从左往右遍历，如果右边的孩子评分比左边的高，那么右边的孩子的糖果数就比左边的多一个
            for (int i = 1; i < ratings.length; i++) {
                if (ratings[i] > ratings[i - 1]) {
                    candies[i] = candies[i - 1] + 1;
                } else {
                    candies[i] = 1;
                }
            }
            // right 表示从右往左遍历的时候第i-1个孩子得到的糖果数
            int right = candies[ratings.length - 1];
            int sum = candies[ratings.length - 1];
            for (int i = ratings.length - 1; i > 0; i--) {
                if (ratings[i - 1] > ratings[i]) {
                    right++;
                } else {
                    right = 1;
                }
                // 从 candies[length - 2] 到 candies[0] 之和
                sum += Math.max(right, candies[i - 1]);
            }
            return sum;
        }
}
